"""冒泡排序"""
def bubble_sort(data_list: list):
    len_list = len(data_list)
    for i in range(len_list - 1):
        # 排序标签: 如果一次内循环中没有发生数据交换, 则表明数据已排好, 可跳出循环
        sort_flag = False
        for j in range(len_list - 1 - i):
            if data_list[j] > data_list[j + 1]:
                data_list[j], data_list[j + 1] = data_list[j + 1], data_list[j]
                sort_flag = True
        if not sort_flag:
            return


"""选择排序"""
def select_sort(data_list: list):
    len_list = len(data_list)
    for i in range(len_list - 1):
        min_loc = i
        for j in range(i + 1, len_list):
            if data_list[min_loc] > data_list[j]:
                min_loc = j
        if min_loc != i:
            data_list[i], data_list[min_loc] = data_list[min_loc], data_list[i]


"""插入排序"""
def insert_sort(data_list: list):
    len_list = len(data_list)
    for i in range(1, len_list):
        temp = data_list[i]
        j = i - 1
        while data_list[i] > temp and j >= 0:
            data_list[j+1] = data_list[j]
            j -= 1
        data_list[j + 1] = temp


"""快速排序"""
def partition(dt_list, left, right):
    """
    :param dt_list: 数据列表
    :param left: 左起点
    :param right: 右起点
    :return:
    """
    temp = dt_list[left]
    while left < right:
        while left < right and dt_list[right] > temp:
            right -= 1
        dt_list[left] = dt_list[right]
        while left < right and dt_list[left] < temp:
            left += 1
        dt_list[right] = dt_list[left]
    dt_list[left] = temp
    return left


def __quick_sort(dt_list, left, right):
    if left < right:
        mid = partition(dt_list, left, right)
        __quick_sort(dt_list, left, mid-1)
        __quick_sort(dt_list, mid+1, right)


def quick_sort(dt_list):
    left = 0
    right = len(dt_list) - 1
    __quick_sort(dt_list, left, right)


"""堆排序"""
def sift(dt_list, low, high):
    i = low
    j = 2 * i + 1
    temp = dt_list[low]
    while j <= high:
        if j+1 <= high and dt_list[j+1] < dt_list[j]:
            j += 1
        if dt_list[j] < temp:
            dt_list[i] = dt_list[j]
            i = j
            j = 2 * i + 1
        else:
            break
    else:
        dt_list[i] = temp


def heap_sort(dt_list):
    len_list = len(dt_list)
    for i in range((len_list-2)//2, -1, -1):
        sift(dt_list, low=i, high=len_list-1)
    for i in range(len_list-1, -1, -1):
        dt_list[0], dt_list[i] = dt_list[i], dt_list[0]
        sift(dt_list, low=0, high=i-1)


"""归并排序"""
def merge(dt_list, low, mid, high):
    i = low
    j = mid + 1
    temp = []
    while i <= mid and j <= high:
        if dt_list[i] < dt_list[j]:
            temp.append(dt_list[i])
            i += 1
        else:
            temp.append(dt_list[j])
            j += 1
    while i <= mid:
        temp.append(dt_list[i])
        i += 1
    while j <= high:
        temp.append(dt_list[j])
        j += 1
    dt_list[low:high+1] = temp


def __merge_sort(dt_list, low, high):
    if low < high:
        mid = (low + high) // 2
        __merge_sort(dt_list, low=low, high=mid)
        __merge_sort(dt_list, low=mid+1, high=high)
        merge(dt_list, low, mid, high)


def merge_sort(dt_list):
    low = 0
    high = len(dt_list)
    __merge_sort(dt_list, low=low, high=high-1)


"""希尔排序"""
def insert_sort_gap(dt_list, gap):
    for i in range(gap, len(dt_list)):
        temp = dt_list[i]
        j = i - gap
        while dt_list[j] > temp and j >= 0:
            dt_list[j + gap] = dt_list[j]
            j -= gap
        dt_list[j + gap] = temp


def shell_sort(dt_list):
    d = len(dt_list) // 2
    while d >= 1:
        insert_sort_gap(dt_list, d)
        d //= 2


"""计数排序"""
def count_sort(dt_list, max_num=100):
    # 需要满足最大值受限的条件
    count = [0 for _ in range(max_num+1)]
    for val in dt_list:
        count[val] += 1
    dt_list.clear()
    for index, val in enumerate(count):
        for i in range(val):
            dt_list.append(index)


"""桶排序"""
def bucket_sort(dt_list, n=100, max_num=10000):
    # n - 桶的个数
    buckets = [[] for _ in range(n)]
    for val in dt_list:
        # i 表示将val放入几号桶中
        i = min((val // (max_num // n)), n-1)
        buckets[i].append(val)
        # 使桶内有序
        for j in range(len(buckets[i])-1, 0, -1):
            if buckets[i][j] < buckets[i][j-1]:
                buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
            else:
                break
        sort_dt_list = []
        for buc in buckets:
            sort_dt_list.extend(buc)
        return sort_dt_list


"""基数排序"""
def radix_sort(dt_list):
    max_num = max(dt_list)
    it = 0
    while 10 ** it <= max_num:
        # 分10个桶[0-9]
        buckets = [[] for _ in range(10)]
        for val in dt_list:
            digit = (val // 10 ** it) % 10
            buckets[digit].append(val)
        dt_list.clear()
        for buc in buckets:
            dt_list.extend(buc)
        it += 1

